package leetcode.erfen;

import leetcode.shuangpoint.Merge;

/**
 给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。

 算法的时间复杂度应该为 O(log (m+n)) 。

 输入：nums1 = [1,3], nums2 = [2]
 输出：2.00000
 解释：合并数组 = [1,2,3] ，中位数 2

 输入：nums1 = [1,2], nums2 = [3,4]
 输出：2.50000
 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

 */
public class FindMedianSortedArrays4 {

    public static void main(String[] args) {
        int [] arr1 = new int[]{1,3};
        int [] arr2 = new int[]{2};

        double res = new FindMedianSortedArrays4().findMedianSortedArrays(arr1, arr2);
        System.out.println(res);

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merge = merge(nums1, nums1.length, nums2, nums2.length);
        System.out.println(merge.length);
        int n = merge.length;

        if(n==1)
            return merge[0];

        if(n==0)
            return 0;

        if(n%2==0)
            return (double)(merge[n/2]+merge[(n/2)-1])/2;

        return (merge[n/2]);
    }

    public int [] merge(int[] nums1, int m, int[] nums2, int n) {
        int []arr = new int[m+n];

        int i = 0,j=0,k=0;
        while (i<m && j<n){
            if(nums1[i]<nums2[j]){
                arr[k++] = nums1[i++];
            }else {
                arr[k++] = nums2[j++];
            }
        }
        while (i<m)
            arr[k++] = nums1[i++];

        while (j<n)
            arr[k++] = nums2[j++];


        return  arr;
    }

}